
<!DOCTYPE html>
<html lang="en" class="loading">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <title>动态规划 - weifan</title>
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="google" content="notranslate" />
    <meta name="keywords" content="TriDiamond Obsidian,"> 
    <meta name="description" content="动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则,"> 
    <meta name="author" content="weifan"> 
    <link rel="alternative" href="atom.xml" title="weifan" type="application/atom+xml"> 
    <link rel="icon" href="/img/favicon.png"> 
    <link href="https://fonts.loli.net/css?family=Roboto+Mono|Rubik&display=swap" rel="stylesheet">
    
<link rel="stylesheet" href="//at.alicdn.com/t/font_1429596_nzgqgvnmkjb.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/animate.css/3.7.2/animate.min.css">

    
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/social-share.js/1.0.16/css/share.min.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/codemirror/5.48.4/codemirror.min.css">

    
<link rel="stylesheet" href="//cdn.bootcss.com/codemirror/5.48.4/theme/dracula.css">

    
<link rel="stylesheet" href="/css/obsidian.css">

    
<link rel="stylesheet" href="/css/ball-atom.min.css">

<meta name="generator" content="Hexo 4.2.1"></head>


<body class="loading">
    <div class="loader">
        <div class="la-ball-atom la-2x">
            <div></div>
            <div></div>
            <div></div>
            <div></div>
        </div>
    </div>
    <span id="config-title" style="display:none">weifan</span>
    <div id="loader"></div>
    <div id="single">
    <div class="scrollbar gradient-bg-rev"></div>
<div id="top" style="display: block;">
    <div class="bar" style="width: 0;"></div>
    <div class="navigation animated fadeIn fast delay-1s">
        <img id="home-icon" class="icon-home" src="/img/favicon.png" alt="" data-url="https://wifidu.gitee.io">
        <div id="play-icon" title="Play/Pause" class="iconfont icon-play"></div>
        <h3 class="subtitle">动态规划</h3>
        <div class="social">
            <!--        <div class="like-icon">-->
            <!--            <a href="javascript:;" class="likeThis active"><span class="icon-like"></span><span class="count">76</span></a>-->
            <!--        </div>-->
            <div>
                <div class="share">
                    
                        <a href="javascript:;" class="iconfont icon-share1"></a>
                        <div class="share-component-cc" data-disabled="facebook,douban,linkedin,diandian,tencent,google"></div>
                    
                </div>
            </div>
        </div>
    </div>
</div>

    <div class="section">
        <div class=article-header-wrapper>
    <div class="article-header">
        <div class="article-cover animated fadeIn" style="
            animation-delay: 600ms;
            animation-duration: 1.2s;
            background-image: 
                radial-gradient(ellipse closest-side, rgba(0, 0, 0, 0.65), #100e17),
                url(/img/cover.jpg) ">
        </div>
        <div class="else">
            <p class="animated fadeInDown">
                
                <a href="/categories/算法"><b>「
                    </b>算法<b> 」</b></a>
                
                June 08, 2020
            </p>
            <h3 class="post-title animated fadeInDown"><a href="/2020/06/08/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/" title="动态规划" class="">动态规划</a>
            </h3>
            
            <p class="post-count animated fadeInDown">
                
                <span>
                    <b class="iconfont icon-text2"></b> <i>Words count</i>
                    12k
                </span>
                
                
                <span>
                    <b class="iconfont icon-timer__s"></b> <i>Reading time</i>
                    11 mins.
                </span>
                
                
                
                <span id="busuanzi_container_page_pv">
                    <b class="iconfont icon-read"></b> <i>Read count</i>
                    <span id="busuanzi_value_page_pv">0</span>
                </span>
                
            </p>
            
            
            <ul class="animated fadeInDown post-tags-list" itemprop="keywords"><li class="animated fadeInDown post-tags-list-item"><a class="animated fadeInDown post-tags-list-link" href="/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a></li></ul>
            
        </div>
    </div>
</div>

<div class="screen-gradient-after">
    <div class="screen-gradient-content">
        <div class="screen-gradient-content-inside">
            <div class="bold-underline-links screen-gradient-sponsor">
                <p>
                    <span class="animated fadeIn delay-1s"></span>
                </p>
            </div>
        </div>
    </div>
</div>

<div class="article">
    <div class='main'>
        <div class="content markdown animated fadeIn">
            <p><strong>动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。</strong></p>
<blockquote>
<p>采用动态规划，必须要知道初始状态和状态转移方程。</p>
</blockquote>
<h2 id="零钱兑换-II"><a href="#零钱兑换-II" class="headerlink" title="零钱兑换 II"></a>零钱兑换 II</h2><p><strong>给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。</strong></p>
<ul>
<li>示例 1:</li>
</ul>
<pre><code>输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1</code></pre><ul>
<li>示例 2:</li>
</ul>
<pre><code>输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。</code></pre><ul>
<li>示例 3:</li>
</ul>
<pre><code>输入: amount = 10, coins = [10] 
输出: 1</code></pre><h3 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h3><p><strong>模板：</strong></p>
<p>这是经典的动态编程问题。这是一个可以使用的模板：</p>
<ul>
<li>定义答案显而易见的基本情况。</li>
<li>制定根据简单的情况计算复杂情况的策略。</li>
<li>将此策略链接到基本情况。</li>
</ul>
<p><strong>例子：</strong></p>
<p>让我们举一个例子：amount = 11，可用硬币面值有 2 美分，5 美分和 10 美分。 请注意，硬币数量是无限的。</p>
<p><img src="/img/suanfa0.jpeg" alt="coins"></p>
<p><strong>基本情况：没有硬币或 金币 = 0</strong></p>
<ul>
<li>如果总金额为 0，那么只有一个组合情况：0。</li>
<li>另一个基本情况是没有硬币，若 amount &gt; 0，则组合情况为 0，若 amount == 0，则组合情况为 1。</li>
</ul>
<p><img src="/img/suanfa1.jpeg" alt="基本情况"></p>
<p><strong>2 美分：</strong></p>
<ul>
<li>让我们用一种硬币做进一步考虑：2 美分</li>
</ul>
<p><img src="/img/suanfa2.png" alt="2 美分"></p>
<ul>
<li>很明显，这里可能会有 1 种或 0 种组合。偶数金额为 1 种，奇数金额为 0 种。</li>
<li>首先，所有金额均小于 2 美分不会受到 2 美分硬币的影响。 因此对于 amount = 0 和 amount = 1 的结果没有变化。</li>
<li>amount = 2 开始，可以使用 2 美分硬币进行组合。</li>
<li>我们使用 2 美分硬币来组合 amount = 2，则金额 2 美分的组合数等于 amount = 0 的组合数量，即 1。</li>
</ul>
<p><img src="/img/suanfa3.jpeg" alt="1"></p>
<ul>
<li>同理 amount = 3 的组合数量等于 amount = 1 的组合数量，即 0。</li>
</ul>
<p><img src="/img/suanfa4.jpeg" alt="0"></p>
<ul>
<li>我们可以推到出 <code>DP</code> 公式为 <code>amount = x: dp[x] = dp[x] + dp[x - coin]</code>，其中 coin = 2 美分，是当前甜腻骄傲硬币的价值。</li>
</ul>
<p><img src="/img/suanfa5.jpeg" alt="2"></p>
<p><strong>2 美分 + 5 美分 + 10 美分：</strong></p>
<ul>
<li>我们先增加 5 美分的情况，公式是一样的。</li>
</ul>
<p><img src="/img/suanfa6.jpeg" alt="5"></p>
<ul>
<li>对于 10 美分也是一样的。</li>
</ul>
<p><img src="/img/suanfa7.jpeg" alt="10"></p>
<p>策略为：</p>
<ul>
<li>从基本情况没有硬币开始，一一添加硬币。</li>
<li>对于每个添加的硬币，我们从金额 0 到 amount 递归的计算组合数量。</li>
</ul>
<p><strong>算法:</strong></p>
<ul>
<li>以基本情况没有硬币开始组合数量。<code>dp[0] = 1</code>，然后其余等于 <code>0</code>。</li>
<li>遍历所有硬币面值：<ul>
<li>对于每个硬币，我们将从金额 0 遍历到 amount：<ul>
<li>对于每个 x，计算组合数：<code>dp[x] += dp[x - coin]</code>。</li>
</ul>
</li>
</ul>
</li>
<li>返回 <code>dp[amount]</code>。</li>
</ul>
<h3 id="Conclusion"><a href="#Conclusion" class="headerlink" title="Conclusion"></a>Conclusion</h3><p>因为我们使用的是一维数组，后面的结果将覆盖前面的结果，所以<code>dp[x] += dp[x - coin]</code>并不是巧合或单纯看图找规律，而是:</p>
<blockquote>
<p>我们将第 <code>i - 1</code> 个硬币记作<code>A</code>, 第 <code>i</code> 个硬币记为<code>B</code></p>
</blockquote>
<p><code>dp[x - coin]</code><strong>(B’s)</strong> 已经在<code>dp[x]</code><strong>(A’s)</strong> 之前已经达到了最大组合数，现在只需要将<code>上个硬币</code>的最大组合数<br><code>dp[x]</code><strong>(A’s)</strong>，加上已经组合好的<code>dp[x - coin]</code><strong>(B’s)</strong> 就是当前的最大组合数。(Because B own coin add to<br><code>dp[x - coin]</code><strong>A or B</strong> ,and it will fit in this case)将<code>DP</code>公式解释一下就是:<br><code>dp[x]</code><em>(B’s)</em> = <code>dp[x]</code><em>(A’s)</em> + <code>dp[x - coin]</code><em>(B’s)</em></p>
<pre><code class="java">class Solution {
  public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;

    for (int coin : coins) {
      for (int x = coin; x &lt; amount + 1; ++x) {
        dp[x] += dp[x - coin];
      }
    }
    return dp[amount];
  }
}</code></pre>
<p><strong>算法复杂度:</strong></p>
<ul>
<li>时间复杂度：O(N×amount)。其中 N 为 coins 数组的长度。</li>
<li>空间复杂度：O(amount)，dp 数组使用的空间。</li>
</ul>
<blockquote>
<p>来源：<a href="https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/" target="_blank" rel="noopener">力扣（LeetCode）</a></p>
</blockquote>
<h2 id="背包问题"><a href="#背包问题" class="headerlink" title="背包问题"></a>背包问题</h2><p><strong>容量：capacity -&gt; C</strong><br><strong>重量：weight   -&gt; w</strong><br><strong>价值：value    -&gt; v</strong></p>
<blockquote>
<p>背包问题上限为<code>重量</code>,硬币上限为<code>金额</code>。</p>
</blockquote>
<blockquote>
<p>参考: <a href="https://www.cnblogs.com/fengziwei/p/7750849.html" target="_blank" rel="noopener">1</a> <a href="https://blog.csdn.net/chanmufeng/article/details/82955730" target="_blank" rel="noopener">2</a></p>
</blockquote>
<h3 id="0-1背包"><a href="#0-1背包" class="headerlink" title="0-1背包"></a>0-1背包</h3><p>0-1背包问题是指每一种物品都只有一件，可以选择放或者不放。现在假设有n件物品，背包承重为m。</p>
<p>对于这种问题，我们可以采用一个二维数组去解决：f[i][j]，其中i代表加入背包的是前i件物品，j表示背包的承重，f[i][j]表示当前状态下能放进背包里面的物品的最大总价值。那么，f[n][m]就是我们的最终结果了。</p>
<p>采用动态规划，必须要知道初始状态和状态转移方程。</p>
<p>初始状态很容易就能知道，那么状态转移方程如何求呢？对于一件物品，我们有放进或者不放进背包两种选择：</p>
<ol>
<li><p>假如我们放进背包，<code>f[i][j] = f[i - 1][j - weight[i]] + value[i]</code>，这里的f[i - 1][j - weight[i]] + value[i]应该这么理解：在没放这件物品之前的状态值加上要放进去这件物品的价值。而对于f[i - 1][j - weight[i]]这部分，i - 1很容易理解，关键是 j - weight[i]这里，我们要明白：要把这件物品放进背包，就得在背包里面预留这一部分空间。</p>
</li>
<li><p>假如我们不放进背包，f[i][j] = f[i - 1][j]，这个很容易理解。</p>
</li>
</ol>
<p>因此，我们的<code>状态转移方程</code>就是：<code>f[i][j] = max{ f[i - 1][j] , f[i - 1][j - weight[i]] + value[i] }</code></p>
<p>当然，还有一种特殊的情况，就是背包放不下当前这一件物品，这种情况下 <code>f[i][j] = f[i - 1][j]</code> 。</p>
<pre><code class="java">public class KnapSack01 {
    public static int knapSack(int[] w, int[] v, int C) {
        int size = w.length;
        if (size == 0) {
            return 0;
        }

        int[][] dp = new int[size][C + 1];
        //初始化第一行
        //仅考虑容量为C的背包放第0个物品的情况
        for (int i = 0; i &lt;= C; i++) {
            dp[0][i] = w[0] &lt;= i ? v[0] : 0;
        }
        //填充其他行和列
        for (int i = 1; i &lt; size; i++) {
            for (int j = 0; j &lt;= C; j++) {
                dp[i][j] = dp[i - 1][j];
                if (w[i] &lt;= j) {
                    dp[i][j] = Math.max(dp[i][j], v[i] + dp[i - 1][j - w[i]]);
                }
            }
        }
        return dp[size - 1][C];
    }

    public static void main(String[] args) {
        int[] w = {2, 1, 3, 2};
        int[] v = {12, 10, 20, 15};
        System.out.println(knapSack(w, v, 5));
    }
}</code></pre>
<p><strong>空间复杂度优化</strong></p>
<p>我们可以知道，当我们利用一维数组进行记忆化的时候，我们只需要使用到当前位置的值和该位置之前的值，举个例子<br>假设我们要计算F(i,4)F(i,4)F(i,4),我们需要用到的值为F(i−1,4)F(i-1,4)F(i−1,4)和F(i−1,4−w(i))F(i-1,4-w(i))F(i−1,4−w(i)),因此为了防止结果被覆盖，我们需要从后向前依次计算结果</p>
<pre><code class="java">public class KnapSack01 {
    public static int knapSack(int[] w, int[] v, int C) {
        int size = w.length;
        if (size == 0) {
            return 0;
        }

        int[] dp = new int[C + 1];
        //初始化第一行
        //仅考虑容量为C的背包放第0个物品的情况
        for (int i = 0; i &lt;= C; i++) {
            dp[i] = w[0] &lt;= i ? v[0] : 0;
        }

        for (int i = 1; i &lt; size; i++) {
            for (int j = C; j &gt;= w[i]; j--) {
                dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
            }
        }
        return dp[C];
    }

    public static void main(String[] args) {
        int[] w = {2, 1, 3, 2};
        int[] v = {12, 10, 20, 15};
        System.out.println(knapSack(w, v, 5));
    }
}</code></pre>
<p>其中有一段代码优化之前如下:</p>
<pre><code class="java">    for (int i = 1; i &lt;= n; i++) {
        for (int j = C; j &gt;= 1; j--) {
            if (weight[i] &lt;= j) {
                f[j] = f[j] &gt; f[j - weight[i]] + value[i] ? f[j] : f[j - weight[i]] + value[i];
            }
        }
    }</code></pre>
<h3 id="完全背包"><a href="#完全背包" class="headerlink" title="完全背包"></a>完全背包</h3><blockquote>
<p>问题关键：因为有无限件物品，所以在 <code>0-1背包</code> 里 <code>f[i - 1][j - weight[i]] + value[i])</code> 是在 <code>i - 1</code> 件物品时最大组合，而我们现在第<code>i</code> 件有n件，所以我们需要用第 <code>i</code> 行的 <code>j - weight</code> 时候的最大组合:  <code>f[i][j - weight[i]] + value[i])</code></p>
</blockquote>
<blockquote>
<p><a href="https://www.pianshen.com/article/7862260614/" target="_blank" rel="noopener">参考</a></p>
</blockquote>
<p><strong>问题叙述：</strong></p>
<p>有n种物品，每种物品的单件重量为w[i]，价值为v[i]。现有一个容量为C的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都有无穷件。</p>
<p><strong>动态规划思想</strong></p>
<p>同样令dp[i][j]表示前i件物品恰好放入容量为v的背包中能获得的最大价值。</p>
<p>和01背包一样，完全背包问题的每种物品都有两种策略，但是也有不同点。对第i件物品来说：</p>
<ul>
<li>不放第i件物品，那么<code>dp[i][j] = dp[i-1][j]</code>，这步跟01背包是一样的。</li>
<li>放第i件物品。这里的处理和01背包有所不同，因为01背包的每个物品只能选择一个，因此选择放第i件物品就意味着必须转移到<code>dp[i-1][j-w[i]]</code>这个状态；但是完全背包问题不同，完全背包如果选择放第i件物品之后并不是转移到<code>dp[i-1][j-w[i]]</code>这个状态；而是转移到<code>dp[i][j-w[i]]</code>，这是因为每种物品可以放任意件（注意有容量的限制，因此还是有限的），放了第i件物品后还可以继续放第i件物品，直到第二维的v-w[i]无法保持大于等于0为止。</li>
</ul>
<p><strong>状态转移方程</strong></p>
<p><code>f[i] = max{f[i], f[i − weight[j]] + value[j]}</code></p>
<p>边界：<code>dp[0][j] = 0 (0 &lt;= j &lt;= C)</code></p>
<p>写成一维形式之后和01背包完全相同，唯一的区别在于这里j的枚举顺序是正向枚举，而01背包的一维形式中j必须是逆向枚举。完全背包的一维形式代码如下所示：</p>
<pre><code class="c++">for(int i = 1 ; i &lt;= n ; i++){
    for(int j = w[i]; j &lt;= C ; j++){
        dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
    }
}</code></pre>
<h3 id="多重背包"><a href="#多重背包" class="headerlink" title="多重背包"></a>多重背包</h3><blockquote>
<p>参考<a href="http://www.luyixian.cn/news_show_24233.aspx" target="_blank" rel="noopener">1</a></p>
</blockquote>
<p><strong>题目：</strong></p>
<p>有N种物品和一个容量为C的背包。第i种物品最多有n[i]件可用，每件费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。</p>
<p><strong>基本算法：</strong></p>
<p>这题目和完全背包问题很像。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件，取2件…取n[i]件。令f[i][j]表示前i种物品恰放入一个容量为j的背包的最大权值。</p>
<p><strong>状态转移方程：</strong><br><code>f[i][j]=max{ f[i - 1][j], f[i - 1][j - k*w[i]] + k*v[i] | 0 &lt;= k &lt;= n[i] }</code></p>
<p>复杂度是<code>O(C * ∑ n[i])</code>。</p>
<pre><code class="c++">#include&lt;iostream&gt;
#include&lt;algorithm&gt;
using namespace std;
const int MAX=1010;
int N,C;
int f[MAX];
int w[MAX],v[MAX],n[MAX]; //费用和价值 
int main()
{
    cin&gt;&gt;N&gt;&gt;C;
    for(int i=1;i&lt;=N;i++)
        cin&gt;&gt;c[i]&gt;&gt;w[i]&gt;&gt;s[i];

    for(int i = 1;i &lt;= N; i++)//N件物品
        for(int j = C;j &gt;= w[i]; j --)
            for(int k = 1;k &lt;= n[i] &amp;&amp; k * w[i] &lt;= j; k ++)
                f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);


    cout&lt;&lt;f[C]&lt;&lt;endl;
}</code></pre>
<h2 id="最大子序和"><a href="#最大子序和" class="headerlink" title="最大子序和"></a>最大子序和</h2><p><strong>给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</strong></p>
<p><strong>示例:</strong></p>
<pre><code>输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。</code></pre><p><strong>进阶:</strong></p>
<p>如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。</p>
<h3 id="题解-1"><a href="#题解-1" class="headerlink" title="题解"></a>题解</h3><p>假设 nums 数组的长度是 n，下标从 0 到 n - 1。</p>
<p>我们用 ai 代表 nums[i]，用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：</p>
<p><code>max {f(i)} 0≤i≤n−1</code></p>
<p>因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？我们可以考虑 ai<br>单独成为一段还是加入 f(i - 1) 对应的那一段，这取决于 ai 和 f(i - 1) + ai<br>的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：</p>
<p><code>f(i) = max { f(i - 1) + ai, ai }</code></p>
<p>不难给出一个时间复杂度 O(n)、空间复杂度 O(n) 的实现，即用一个 f 数组来保存 f(i) 的值，用一个循环求出所有 f(i)。考虑到 f(i) 只和<br>f(i - 1) 相关，于是我们可以只用一个变量 pre 来维护对于当前 f(i) 的 f(i−1) 的值是多少，从而让空间复杂度降低到 O(1)，这有点类似「滚动<br>数组」的思想。</p>
<pre><code class="javascript">var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) =&gt; {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;
};</code></pre>
<p>复杂度</p>
<p>时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。<br>空间复杂度：O(1)。我们只需要常数空间存放若干变量。</p>
<p>来源：<a href="https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/" target="_blank" rel="noopener">力扣（LeetCode）</a></p>

            <!--[if lt IE 9]><script>document.createElement('audio');</script><![endif]-->
            <audio id="audio" loop="1" preload="auto" controls="controls"
                data-autoplay="false">
                <source type="audio/mpeg" src="">
            </audio>
            
            <ul id="audio-list" style="display:none">
                
                
                <li title='0' data-url='/statics/chengdu.mp3'></li>
                
                    
            </ul>
            
            
            
    <div id='gitalk-container' class="comment link"
        data-ae='true'
        data-ci='ec894e2b66f752e8b7fb'
        data-cs='3ccc2e92bb350688fe2c2dc2930189b62622bfb1'
        data-r='blog-comments'
        data-o='TriDiamond'
        data-a='TriDiamond'
        data-d=''
    >Comments</div>


            
            
        </div>
        <div class="sidebar">
            <div class="box animated fadeInRight">
                <div class="subbox">
                    <img src="/img/mei.jpeg" height=300 width=300></img>
                    <p>weifan</p>
                    <span>Think like an artist, develop like an artisan</span>
                    <dl>
                        <dd><a href="https://github.com/wifidu" target="_blank"><span
                                    class=" iconfont icon-github"></span></a></dd>
                        <dd><a href="" target="_blank"><span
                                    class=" iconfont icon-twitter"></span></a></dd>
                        <dd><a href="" target="_blank"><span
                                    class=" iconfont icon-stack-overflow"></span></a></dd>
                    </dl>
                </div>
                <ul>
                    <li><a href="/">7 <p>Articles</p></a></li>
                    <li><a href="/categories">6 <p>Categories</p></a></li>
                    <li><a href="/tags">6 <p>Tags</p></a></li>
                </ul>
            </div>
            
            
            
            <div class="box sticky animated fadeInRight faster">
                <div id="toc" class="subbox">
                    <h4>Contents</h4>
                    <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#零钱兑换-II"><span class="toc-number">1.</span> <span class="toc-text">零钱兑换 II</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#题解"><span class="toc-number">1.1.</span> <span class="toc-text">题解</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Conclusion"><span class="toc-number">1.2.</span> <span class="toc-text">Conclusion</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#背包问题"><span class="toc-number">2.</span> <span class="toc-text">背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#0-1背包"><span class="toc-number">2.1.</span> <span class="toc-text">0-1背包</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#完全背包"><span class="toc-number">2.2.</span> <span class="toc-text">完全背包</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#多重背包"><span class="toc-number">2.3.</span> <span class="toc-text">多重背包</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#最大子序和"><span class="toc-number">3.</span> <span class="toc-text">最大子序和</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#题解-1"><span class="toc-number">3.1.</span> <span class="toc-text">题解</span></a></li></ol></li></ol>
                </div>
            </div>
            
            
        </div>
    </div>
</div>

    </div>
</div>
    <div id="back-to-top" class="animated fadeIn faster">
        <div class="flow"></div>
        <span class="percentage animated fadeIn faster">0%</span>
        <span class="iconfont icon-top02 animated fadeIn faster"></span>
    </div>
</body>
<footer>
    <p class="copyright" id="copyright">
        &copy; 2020
        <span class="gradient-text">
            weifan
        </span>.
        Powered by <a href="http://hexo.io/" title="Hexo" target="_blank" rel="noopener">Hexo</a>
        Theme
        <span class="gradient-text">
            <a href="https://github.com/TriDiamond/hexo-theme-obsidian" title="Obsidian" target="_blank" rel="noopener">Obsidian</a>
        </span>
        <small><a href="https://github.com/TriDiamond/hexo-theme-obsidian/blob/master/CHANGELOG.md" title="v1.4.3" target="_blank" rel="noopener">v1.4.3</a></small>
    </p>
</footer>

<script type="text/javascript" src="https://cdn.bootcss.com/mathjax/2.7.6/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script>
  MathJax.Hub.Config({
    "HTML-CSS": {
      preferredFont: "TeX",
      availableFonts: ["STIX", "TeX"],
      linebreaks: {
        automatic: true
      },
      EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
      inlineMath: [
        ["$", "$"],
        ["\\(", "\\)"]
      ],
      processEscapes: true,
      ignoreClass: "tex2jax_ignore|dno",
      skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
      noUndefined: {
        attributes: {
          mathcolor: "red",
          mathbackground: "#FFEEEE",
          mathsize: "90%"
        }
      },
      Macros: {
        href: "{}"
      }
    },
    messageStyle: "none"
  });
</script>
<script>
  function initialMathJax() {
    MathJax.Hub.Queue(function () {
      var all = MathJax.Hub.getAllJax(),
        i;
      // console.log(all);
      for (i = 0; i < all.length; i += 1) {
        console.log(all[i].SourceElement().parentNode)
        all[i].SourceElement().parentNode.className += ' has-jax';
      }
    });
  }

  function reprocessMathJax() {
    if (typeof MathJax !== 'undefined') {
      MathJax.Hub.Queue(["Typeset", MathJax.Hub]);
    }
  }
</script>



    
<link rel="stylesheet" href="//cdn.bootcss.com/gitalk/1.5.0/gitalk.min.css">

    
<script src="//cdn.bootcss.com/gitalk/1.5.0/gitalk.min.js"></script>



<script src="//cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>
<script src="/js/plugin.js"></script>
<script src="/js/obsidian.js"></script>
<script src="/js/jquery.truncate.js"></script>
<script src="/js/search.js"></script>


<script src="//cdn.bootcss.com/typed.js/2.0.10/typed.min.js"></script>


<script src="//cdn.bootcss.com/blueimp-md5/2.12.0/js/md5.min.js"></script>


<script src="//cdnjs.cloudflare.com/ajax/libs/social-share.js/1.0.16/js/social-share.min.js"></script>


<script src="https://cdn.bootcss.com/codemirror/5.48.4/codemirror.min.js"></script>

    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/javascript/javascript.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/css/css.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/xml/xml.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/htmlmixed/htmlmixed.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/clike/clike.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/php/php.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/shell/shell.min.js"></script>


    
<script src="//cdn.bootcss.com/codemirror/5.48.4/mode/python/python.min.js"></script>




    
<script src="/js/busuanzi.min.js"></script>

    <script>
        $(document).ready(function () {
            if ($('span[id^="busuanzi_"]').length) {
                initialBusuanzi();
            }
        });
    </script>



<link rel="stylesheet" href="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe.min.css">
<link rel="stylesheet" href="//cdn.bootcss.com/photoswipe/4.1.3/default-skin/default-skin.min.css">


<script src="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe.min.js"></script>
<script src="//cdn.bootcss.com/photoswipe/4.1.3/photoswipe-ui-default.min.js"></script>


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>
    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">
        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>
        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">
            <div class="pswp__top-bar">
                <!--  Controls are self-explanatory. Order can be changed. -->
                <div class="pswp__counter"></div>
                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
                <button class="pswp__button pswp__button--share" title="Share"></button>
                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                      <div class="pswp__preloader__cut">
                        <div class="pswp__preloader__donut"></div>
                      </div>
                    </div>
                </div>
            </div>
            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div> 
            </div>
            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>
            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>
            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>
        </div>
    </div>
</div>



    <!-- Global site tag (gtag.js) - Google Analytics -->
    <script async src="//www.googletagmanager.com/gtag/js?id=UA-149874671-1"></script>
    <script>
        window.dataLayer = window.dataLayer || [];
        function gtag(){dataLayer.push(arguments);}
        gtag('js', new Date());

        gtag('config', 'UA-149874671-1');
    </script>





<script>
    function initialTyped () {
        var typedTextEl = $('.typed-text');
        if (typedTextEl && typedTextEl.length > 0) {
            var typed = new Typed('.typed-text', {
                strings: ["Think like an artist, develop like an artisan", "艺术家思维去思考问题，工匠创造精神去开发"],
                typeSpeed: 90,
                loop: true,
                loopCount: Infinity,
                backSpeed: 20,
            });
        }
    }

    if ($('.article-header') && $('.article-header').length) {
        $(document).ready(function () {
            initialTyped();
        });
    }
</script>




</html>
